1. Field of the Invention
This invention relates in general to an accessing method for address data and a network switching apparatus using the same. More particularly, the invention provides a method and apparatus for accessing a non-symmetric dual-slot address table.
2. Description of Related Art
To access the internet, a hardware interface responsible for tranceiving is required. In general, except the home users usually use modems to access the internet, other network systems are connected to each other by network cards. For example, many personal computers (PC) are connected to servers through the network cards, and then connected to the network through the servers. Therefore, the network card is a media, through which the PCs can be connected to the network.
FIG. 1 shows a schematic diagram that two PCs are connected via the network. As shown, the PC 130 and the PC 150 are connected by the network 100, i.e. the two PCs can communicate to each other to transfer data. Due to the limited bandwidth, prior to transmitting data, the data is divided into many small packets to facilitate data transmission. In each packet, a media access control (MAC) address of the PC is recorded for telling where the packet is transmitted from and where the packet is transmitted to in order to prevent the packet lost. Simply speaking, each network card in each PC records the MAC address of the PC, which is like an address number (the MAC address). When the data is transmitted through the network, the packets can be continuously transmitted to the correct destination according to the specified MAC address, such that the data can be surely transmitted.
FIG. 2 shows a schematic diagram of a packet. The packet 200 stores information of MAC address 210. In general, the MAC address information 210 contains a source MAC (SMAC) address 210a and a destination MAC (DMAC) 210b address, according to which the data transmission can be executed. Referring to FIGS. 1 and 2, if the PC 130 is at a port 13 and intends to transmit data to the PC 150 at a port 15 through the network 100, the PC 130 divides the data into a plurality of packets 200. In each packet 200, the MAC address information 210 shows that the SMAC address 210b is 130 (the source of the packet is the PC 130) and the DMAC address 210a is 150 (the destination of the packet is the PC 150). Then, a network switching device looks up an address table (not shown) according to the DMAC address 210a to know that the PC 150 is at the port 15, thereby the packet 200 is transmitted to the PC 150. As described above, prior to the data transmission, the address information of a remote PC must be found by referring to the address table. The network switching device has a memory to store such an address table for storing a plurality of MAC addresses to facilitate data transmission.
FIG. 3A is a structure of an address table stored in the memory. In the memory of each switching device, a particular area is allocated as the address table 310 for storing the MAC address information of computers on the network. The MAC address content has been described above, which will not be explained here. Because the address table 310 uses a certain region of the memory 300, the size can be varied according to different demands, for example 4K or 8K etc. Taking a 4K address table as an example, the memory 300 can allocate 4K addresses (0 to 4K−1) to the address table 310 for storing the MAC address information. Therefore, the address table 310 has 4K buckets for storing 4K different MAC address information respectively. For simplicity, the numbers for the buckets and the memory addresses are the same. For example, address 0 corresponds to the entry 0, address 1 corresponds to the entry 1 . . . and address 4K−1 corresponds to the entry 4K−1. Namely, in the memory 300, the 4K buckets correspond to 4K addresses 0 to 4K−1, respectively. In the following paragraph, the method for writing the MAC address information to the address table is described.
FIG. 3B shows a method for writing to the address table in FIG. 3A. Prior to writing a SMAC address to an entry, a CRC hash operation is performed to obtain a hash value. Next, to find an address in the address table 310 corresponding to the hash value, the SMAC address information is written to that address. In order that the hash values correspond to the 4K addresses one by one, a 12-bit CRC hash operation is performed so that the obtained hash value has also 12 bits. According to the various hash values, 4K addresses can be mapped onto correspondingly. In practice, the SMAC address with 48 bits is used for calculating the hash value, and then the SMAC address and the source port information are written to the corresponding entry to facilitate the table look-up.
For example, assume that a PC A is at port 5 and its SMAC address is A, a PC B is at port 7 and its SMAC address is B. After the PC A and the PC B are connected by the switching device, the switching device calculates the SMAC address (A) of the PC A according to the CRC hash operation to obtain a hash value, for example 20. Afterwards, the switching device writes the SMAC address information of the PC A (A) and the source port (5) to the entry 20 of the address table. When the PC A intends to transmit the packets, that SMAC=A and DMAC=B are stored therein, to the PC B, the switching device perform the CRC hash operation to the DMAC address (B) to obtain a hash value, for example 35. Then, an entry 35 is found according to the hash value 35, in which the source port (7) of the PC B has already been recorded. Accordingly, the packet can be transmitted to the port 7 to complete the packet transmission. It should be noticed that the hash values calculated from the various 48-bits SMAC addresses by the 12 bit CRC hash operation are not one-to-one correspondence for those SMAC addresses. Namely, after the CRC hash operation, a 48 bit data is reduced to an expression of 12 bit hash value, which means that some information in the 48 bits disappear. Therefore, it is highly possible that two SMAC addresses may have the same hash value after the CRC hash operation. However, because each address in the address table can only store one MAC address information, one of the MAC addresses may be abandoned if two SMAC addresses have the same hash value, thereby causing data lost. To compensate the drawback, the conventional method makes the 4K addresses in the memory correspond to 2K buckets, which will be described in the following paragraph.
FIG. 4A shows a structure of a conventional dual-slot address table. Taking a 4K address table as an example, the 4K addresses (0 to 4K−1) are assigned to an address table 410. In the design, each entry has two slots: slot 0 and slot 1. Namely, 2K buckets can store 4K address data. It should be noticed that the address table 410 is a symmetric dual-slot address table because the address table 410 is composed of two slots having equal size. FIG. 4B shows a method for writing to the address table in FIG. 4A. As shown, after a SMAC address is operated by the CRC hash operation, the obtained hash value is 1K such that the address data is written to the entry 1K of the address table. However, there are tow slots corresponding to the hash value 1K, the address data is priorly written to the slot 0, rather than the slot 1. If there is another MAC address of the network card has the same hash vale of 1K after the 11 bit CRC hash operation, the later MAC address will be written to the slot 1 also corresponding to the hash value of 1K. Accordingly, the later MAC address data will not be lost. In short, when the MAC address is written to the corresponding slot, the slot 0 is first used for writing. If the slot 0 has stored data, then the data will be written to the slot 1. The advantage of this method is that even if two different SMAC addresses have the same hash value after the CRC hash operation, the two SMAC addresses can still be written to the same entry but different slots, thereby the address data will not be lost.
On the other hand, during the packet transmission, in order to ensure that the packet can be properly transmitted to the remote computer, the port number for the remote computer can be obtained according to the records of the DMAC address in the packet while the packet is transmitting. The method has been discussed above, and their details are omitted here. A hash value corresponding to the DMAC address can be found by performing the CRC hash operation. Under the dual-slot configuration, an address information corresponding to the hash value is first found in the address table, and the SMAC address information in the slot 0 corresponding the address is read to determine whether the DMAC and the SMAC addresses are matched. If matched, it means that the recorded source port in slot 0 is the destination of the packet, by which the packet can be transmitted. If not matched, the SMAC address information in the slot 1 corresponding the address is further read to determine whether the DMAC and the SMAC addresses are matched. If matched, it means that the recorded source port in slot 1 is the destination of the packet, by which the packet can be transmitted. However, if the SMAC addresses in the slot 0 and the slot 1 corresponding to the same hash value are not consistent to the DMAC address, the packet is then sent by the broadcast. It should be noticed that the read SMAC address information is not the whole 48 bits SMAC address, but only the significant bits of the SMAC address and the source port. For example, currently, the higher 37 bits (the MAC tag) in the SMAC address are stored, and the lower 11 bits in the SMAC address are not stored. The hash operation will not create that two different MAC addresses have the same hash value and the same MAC tag (MAC[47:11]), but different MAC[10:0]. To retrieve the SMAC address, the hash value and the MAC tag in the slot are operated. However, this mathematical operation is not the points of the invention, which is omitted here.
As described above, in order to prevent from losing one of the SMAC addresses having the same hash value, the address table can be divided into two parts to form two corresponding slots for each entry, so each entry in the address table corresponds to two slots. Therefore, two different MAC addresses having the same hash value are written to the slot 0 and the slot 1 respectively to prevent the data from lost. In addition, because the addresses of the address table correspond to the hash values and the range of the hash values is determined by the bit number of the CRC function, the size of the address table has to be power of 2, such as 2K, 4K, 8K, 16K, if the size of the address table is based on the unit of 1K (210). Accordingly, the size of the address table cannot be adjusted very flexible. In other word, the foregoing method cannot support an address table having a size of an integer multiple of 2. In U.S. Pat. No. 5,920,900, it provides a Hash-based translation method and apparatus with multiple level collision resolution. The conversion method uses a programmable hash technology of an input value to generate a hash value. If a collision occurs in a resolution table, a new resolution table is generated. This procedure is repeatedly performed until all input values are converted. However, this method is too complicated to be implemented by hardware.
In summary, the access method for conventional address table cannot support all the address table having a size of the integer multiple of 2, such as 6K, 10K. In addition, the memory in the switching device cannot be assigned flexibly.